Upon compression-encoding image data, it is a common practice to compress data by exploiting the fact that neighboring pixel data are more likely to have an identical value.
As one of such compression methods, a runlength encoding technique is known. Runlength encoding encodes a runlength of identical data that runs and the data themselves. As another compression method, a method using delta row encoding is known. Delta row encoding encodes a runlength when data identical to that in the immediately previous line run. As still another compression method, prediction encoding is known. This prediction encoding calculates a predicted value of a pixel of interest from several neighboring pixels, e.g., left and upper pixels, and encodes a difference between the pixel value of interest and predicted value, i.e., a prediction error. In addition, various other compression methods which refer to neighboring pixels have been proposed.
When a grayscale image which is expressed by 8 bits (256 gray levels) per pixel is reduced to a grayscale image which is expressed by 4 bits (16 gray levels) per pixel, it is a common practice to reduce colors by performing a calculation process, using a dither matrix, based on different threshold values for respective pixels in each matrix. When color reduction is made using such dither matrix, even when neighboring pixel values in an original image are equal to each other, different threshold values are used in color reduction of neighboring pixels. Hence, neighboring pixel values after color reduction normally have different values, and a high compression ratio cannot be expected by the aforementioned method.
Since the dither matrix is applied repetitively, separate pixels (normally, pixels separated by a dither matrix period (size)) have high correlation in place of neighboring pixels. Therefore, in order to solve this problem, pixels which are separated by the dither matrix size need only be referred to in place of neighboring pixels.
As such color reduction process having periodicity, a halftone process is known in addition to the dither process. The halftone process is also an image processing method which determines output pixel values by comparing threshold values that repeat periodically with input pixel values.
In order to reduce this problem, a so-called interlaced process that rearranges scan lines in accordance with the dither matrix period is known. For example, when a 4×4 (pixel) dither matrix is used, scan lines are rearranged at intervals for four lines, so that pixels having high correlation align in the vertical direction. However, correlation cannot be improved in the horizontal direction, and an extra process, i.e., rearrangement, must be additionally done, resulting a long encoding processing time.
Furthermore, a technique for rearranging pixels in the horizontal direction in accordance with the dither matrix period is also known (e.g., Japanese Patent No. 2694826). However, according to this method, although pixels having high correlation are rearranged in the horizontal direction, correlation cannot be improved in the vertical direction, and an extra process, i.e., rearrangement, must be additionally done. In addition, since rearrangement for respective pixels must be done, if each pixel is expressed by less than 8 bits, an overhead is large if the process is done by a normal computer.
Moreover, a technique for referring to pixels having high correlation with reference to neighboring blocks without rearranging data is known (e.g., Japanese Patent Laid-Open No. 8-223428). However, according to this embodiment, vertical correlation cannot be utilized. Hence, a high compression ratio cannot be set for an image which has low horizontal correlation and high vertical correction, e.g., an image which has vertical stripes whose width is equal to the block width.
In addition, a prediction technique that uses the pixel values of a neighboring pixel group is known (e.g., Japanese Patent Laid-Open No. 2003-174561). However, upper pixels must be referred to so as to apply effective compression to the vertical stripe image, and a memory having a certain capacity is required.
In addition, various encoding methods such as LZ77 encoding, LZ78 encoding, JBIG encoding, JPEG encoding, and the like have been proposed. In either of these methods, encoding requires a large calculation volume, and also a considerably long period of time when an image is encoded by software. Also, when decoding is done by hardware, the circuit scale of a decoder increases.